1. Field of the Invention
The present invention relates to a neural network for efficiently solving combination optimization problems.
2. Description of the Related Art
In recent years, as a method of realizing an information processing capability resembling a man's right brain, a neural network has received a great deal of attention. The neural network models upon neurons and is constituted by a large number of artificial neurons connected to each other. These artificial neurons weight input signals, calculate a total sum of the weighted input signals, and generate an output by processing the total sum in accordance with a nonlinear function.
In a general neural network, a processor is assigned to the artificial neurons, subtracts a predetermined value from the input weighted sum signal, and outputs a function value as a result of subtraction. Note that neurons which process an analog value have a membrane potential. Artificial synapses constituted by multipliers are connected to the neurons, respectively. These synapses have connection weights between pairs of neurons. Each synapse multiplies the input signal with its own weighting and outputs the product to the neurons connected to itself.
The above neural network is said to be suitable for solving combination optimization problems. The combination optimization problems are raised to determine various methods which result in minimum costs under predetermined conditions. The combination optimization problems are exemplified by Traveling-Salesman Problems (i.e., a problem for determining a minimum distance of one salesman who travels through n cities), and LSI layout problems (i.e., a problem for determining a minimum number of cuts in a circuit division).
In order to solve the combination optimization problems using neural networks, a Hopfield technique is generally employed. This technique is disclosed in J. J. Hopfield, Neural Networks Physical System with Emergent Collective Computation Abilities, Proceedings of the National Academy of Sciences, vol. 79, pp. 2554-2558, 1982, and J. J. Hopfield, Neuron with Graded Response Have Collective Computational Properties like Those of Two-State Neurons, Proceedings of the National Academy of Sciences, vol. 81, pp. 3088-3092, 1984.
In order to solve each combination optimization problem using a neural network in accordance with the Hopfield technique, weightings obtained by an energy function are respectively designated for a plurality of artificial synapses, and the neural network performs repeated computation. This repeated computation allows the neural network to converge to a given state. If the converged state is not appropriate, the parameter within the energy function is adjusted, so that computation continues until the neural network is converged to an optimal state while a weighting value is continuously changed. According to this conventional method, since the parameter value within the energy function cannot be predetermined, a large volume of computation is required to determine the optimal weighting, and solutions for optimization problems cannot be efficiently derived.